\documentclass[12pt, BCOR12mm, pdftex, DIV=calc, parskip=half]{scrartcl}

\usepackage[utf8]{inputenc}
\usepackage[ngerman]{babel}

\begin{document}
\section{Algorithmus}
Wir codieren die Reihenfolge der Städte mit einer Kette von Buchstaben. \textit{A} steht für New York, \textit{B} für Los Angeles usw.
Ein gültiger Plan ist dann eine Liste, die jeden Buchstaben von \textit{A} bis \textit{R} einmal enthält. 
Für die Bewertung werden dann die Distanzen der aufeinanderfolgenden Städte addiert:
\[F(ABCD) = d_{a,b} + d_{b,c} + d_{c,d} +d_{d,a}\]
Der letzte Summand vervollständigt dabei die Rundreise.

Für die nächste Generation werden nun zwei Pläne kombiniert. Dazu werden vom ersten Plan die jeweils vier ersten und letzten Stellen gestrichen
und in der Reihenfolge, in der sie im zweiten Plan auftauchen, wieder angefügt. Beispiel:
\[(ABCDEFGHIJKLMNOPQR) x (AKLMNOPEFGHIJBQRCD) = (AOPB EFGHIJKLMN QRCD)\]

Eine Mutation wird ausgeführt, indem zwei zufällige Städte vertauscht werden. Ist der entstehende Plan schon Teil der Generation, wird so lange mutiert, bis ein neuer Plan entsteht.

Für die Erzeugung einer neuen Generation werden die Elemente paarweise gekreuzt und es werden die fünf besten Pläne der Elterngeneration direkt als Elite übernommen. Anschließend werden die 25 besten Pläne, sowie ein zufälliger Plan, behalten.

Der Algorithmus beginnt mit einer initialen Generation aus 18 zufälligen Plänen und 18 Plänen, die entstehen, wenn man jeweils von einer der Städte ausgehend immer die nächstgelegene Stadt, die noch nicht Teil des Plans ist, zum Plan hinzufügt.
\section{Zusatzfrage: Was verändert sich, wenn Sie jede Stadt nur genau einmal besuchendürfen?}
Im Falle von echten Städten ist die direkte Verbindung zwischen diesen immer die kürzeste. 
Wenn Städte also mehrmals besucht werden können, vergrößert dies nur unnötig den Lösungsraum um Lösungen, die immer schlechter sind als eine Variante mit gleicher Reihenfolge aber ohne Wiederholungen.
Geht man allerdings nicht von Städten, sondern von allgemeinen gerichteten Graphen aus, die die Eigenschaft des direkten Weges nicht haben, kann es sinnvoll sein, die Rückkehr zu Knoten zu erlauben, um bessere Lösungen zu finden, 
auch wenn dies den Lösungsraum vergrößert.
\end{document}

